package com.sise.Array;

/**
 *      26. 删除有序数组中的重复项
 *
 *      给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
 *      不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
 *
 *      输入：nums = [0,0,1,1,1,2,2,3,3,4]
 *      输出：5, nums = [0,1,2,3,4]
 *      解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
 *
 *      题解：要求删除重复元素，实际上就是将不重复的元素移到数组的左侧
 *      使用两个指针 slow、fast，比较两个值是否相等：
 *      1、如果 slow = fast，那么 fast 往前移动一步
 *      2、如果 slow != fast，那么将 fast 的值赋值给 slow，然后 slow 和 fast 都往后移动一步
 *      3、直到 fast 到达 数组最终位置 n
 *
 */
public class _26_removeDuplicates {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int fast = 1;
        int slow = 1;

        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {         // 由于数组是有序相连的，如果相邻数值不相等，那么就说明此时出现 不同的数值
                nums[slow] = nums[fast];                // 将此时 fast 的数值赋值给 slow
                ++slow;                                 // slow 往后移动一步
            }
            ++fast;                                     // 无论数值相等还是不相等，fast都会往后移动
        }
        return slow;
    }
}
